﻿#pragma once
​
一：题目




解释：给你一个数组，再给你两个值(会给m次)，这两个值是一段区间的左右边界，求区间的和





二：算法
一切的前提都是我们创建的接收题目数组的数组，假设为arr，是多一个空间，从下标1开始使用

1：暴力
暴力解法很简单，给我们LR，我们就从arr数组的下标L一直累加到下标R

而暴力的最差情况，就是询问我们m次，每次给的L和R就是整个arr数组下标1到n，也就是整个每次都让你求整个数组的大小，所以暴力时间复杂度为O(m.n)

Q：为什么你说R会为n ?

A：题目认定了下标从1开始，所以题目可以给n，代表数组最后一个元素！

2：前缀和
①：前缀和求区间和的速度
前缀和算法的核心思想：用空间换时间。它通过预先计算并存储一个“前缀和数组”，使得之后计算任意区间和的操作可以在常数时间(O(1))内完成。

我们用一个具体的例子来说明：



前缀和：就是dp[i]等于原始数组中第一个到第i个元素的和，比如dp[3] = 7，代表7等于原始数组中从第一个元素到第3个元素的和，也就是2 + 4 + 1 = 7！

Q1：为什么dp要多开辟一个空间，然后把下标为0位置空着，从下标为1位置开始使用？

A1：这是前缀和的固定做法，这样设计的好处有两个：

①：不用担心边界的处理，这点在后面会谈到

②：这样设计dp[i]才能代表原始数组中第一个元素到第i个元素的和！也就是前i个元素的和

图示如下：



注：dp[i]中的i是pd数组的下标，而arr从第一个到第i个的i，是元素的数量，所以不要混淆

Q2：那这样请问对题目有什么帮助？

A2：题目问得就是第L个元素到第R个元素的和，而我们有了fd数组，我们只需要dp[R] - dp[L - 1]，就能求到题目问的第L个元素到第R个元素的和！

比如现在题目问我们L是2，R为4，也就是第二个元素到第四个元素这段区间的和，则我们只需要fd[R] - fd[L - 1]，也就是fd[4] - fd[1]就是答案！

因为这相当于你在一段大区间（arr的2, 4, 1, 6）里面求一段小区间的和（arr的4, 1, 6），则你只需使用大区间（arr的2, 4, 1, 6）减去另外一段小区间（arr的2）的和即可，所以这也是为什么dp[R] - dp[L - 1]中的L需要 - 1的原因，因为另外段小区间（arr的2）的和，就是dp数组中L下标的前一个小标对应的元素，也就是dp[L - 1]！

图解如下：



所以，不管题目的LR是多少，我们只需返回dp[R] - fd[L - 1]的值即可！时间复杂度为O(1)，而查询了m次，所以总的时间复杂度为O(m)，而创建前缀和数组的空间复杂度为O(n)

时间复杂度：O(m)

空间复杂度：O(n)

所以远比O(m.n)优秀得太太太太多~~，这就是空间换时间！

②：前缀和数组怎么创建
所以，现在的问题在于怎么创建前缀和，很显然，要求dp[i]的值，我们不能每次都是从arr数组中的第一个累加到第i个，如果arr数组很长，则我们创建前缀和数组的时间复杂度为O(n ^ 2)，超时！

a：原始数组从下标0开始使用
而dp[i] 的定义是：存储原数组 arr 中前 i 个元素的和。

并且，我们的dp的第一个元素是不用的，dp数组从1下标开始使用，此时arr和dp数组对应关系如下



此时的公式为：dp[i] = dp[i - 1] + arr[i - 1]，其中dp[i]说白了就是比dp[i - 1]要多加上一个arr里面的数，这个数就是arr[i - 1]！

这样的确符合fd[i] 的定义是：存储原数组 arr 中前 i 个元素的和。

但是不太好记，不太优雅，如果是dp[i] = dp[i - 1] + arr[i]的话，那就太好了，这就很好记， 求dp[i]就是dp[i - 1] + arr[i]即可，我们dp[i]中的i是几，则dp[i - 1] + arr[几]就行!并且这也是前缀和的标准公式，那怎么才能达到这个公式呢？？

b：原始数组从下标1开始使用


也就是我们使用arr数组接收题目给我们的原始数组的时候，我们让arr和dp数组一样，也是多开一个空间，然后从下标1开始使用！

现在的公式就变成了：dp[i] = dp[i - 1] + arr[i]

Q：你把原始数组arr强行的多开辟一个，此时不是dp[i]就不能代表原始数组arr的前i个元素的了吗？因为arr在0位置多了一个元素啊？

A：arr是用来接收题目给我们的原生数组的，arr不是原生数组，所以arr是否多开辟一个空间，和dp[i]代表原始数组的前i个元素之间，不会互相影响，而arr多开辟一个空间，玩完全是为了我们创建前缀和数组时候的公式好看一点！

最后我想说，其实这两种写法，都是一样的效果，都不会进行边界的判断，为什么？因为不管是dp[i] = dp[i - 1] + arr[i - 1] 还是 dp[i] = dp[i - 1] + arr[i] ，这两个公式的i最小都是固定为1的，因为我们的dp数组的下标就是从1开始使用的！所以[]里面的下标最小也是0，不会越距！

三：题目的L和R
我们谈了arr和dp数组都应该多开辟一个空间，从下标为1处开始使用，这意味这，

创建前缀和数组的公式为：dp[i] = dp[i - 1] + arr[i]

求LR区间的和的公式为：dp[R] - dp[L - 1]

现在还剩最后一个问题！

Q：题目规定L或R为1的时候，代表数组的第一个元素，如果L或R是0代表数组的第一个元素呢？题目的输入约定，会对我们现有的思路造成影响吗？

A：会！

题目约定1还是0代表第一个元素；

约定1，也就是题目想直接用L和R表示第几个罢了；

约定0，则代表题目想用L和R表示下标罢了；

例子：比如 L = 1， R = 3；

约定1：数组的第1个元素到第三个元素的和为多少？

约定0：数组从下标为1到下标为3的元素的和为多少？



所以答案是不一样的！后者约定0求得区间是相较于约定1的区间，向后错位1个位置，也就是我们的求和公式dp[R] - dp[L - 1]不对了，那怎么办？很简单，既然你约定0，求的区间整体向后移动1个位置，那我们的公式仍然为dp[R] - dp[L - 1]！不过，L和R需要在使用公式正确双双 + 1！

所以不管题目约定的是什么，我们心里要清楚，dp[i]代表的是题目给的数组的前i个数的和即可！所以我们只需要把L和R转换为L指的是第几个数，R指的是第几个数，而约定1，L和R就是代表的第几个数，而约定0，则L和R需要双双 + 1，然后再使用dp[R] - dp[L - 1]

四：总结前缀和算法
1：创建前缀和数组
前缀和数组bp一定要从下标1开始使用，其次接收原生数组的arr数组也要从下标1开始使用，

这样的好处在于：

①：dp[i]代表原生数组的前i个元素的和

②：创建前缀和数组公式为：dp[i] = dp[i - 1] + arr[i]

不推荐！：而你若是想让arr从0开始，也就是直接接收原生数组，也可以，不过创建前缀和数组的公式为：dp[i] = dp[i - 1] + arr[i - 1]

2：使用前缀和数组
求区间的和的公式恒定为：dp[R] - dp[L - 1]

而题目约定1为原生数组的初始元素，则直接使用dp[R] - dp[L - 1]

若题目约定0为原生数组的初始元素，则先让L和R双双++，然后再使用dp[R] - dp[L - 1]；

不推荐！：当然，你也可以在使用公式的时候再++，也就是 dp[R + 1] - dp[L]

五：代码
1：arr从下标为1处开始
#include <iostream>
#include<vector>
using namespace std;


//创建的arr 和 dp 都从下标1开始使用
int main() {

	int n;//接收数组的元素个数
	int q;//接收查询次数
	cin >> n >> q;

	vector<int> arr(n + 1); //创建arr数组来接受传进来的数组 从arr数组的下标1处开始接收
	for (int i = 1; i < n + 1; i++) {
		cin >> arr[i];
	}

	vector<long long> dp(n + 1);//预处理dp数组 dp数组从1开始存储元素
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1] + arr[i];
	}

	int l, r;//查询区间的左右边界

	while (q--) {//进行q次查询 没
		cin >> l >> r;
		cout << dp[r] - dp[l - 1] << endl;
	}

}
2：arr从下标为0处开始
#include <iostream>
#include<vector>
using namespace std;


//创建的arr 和 dp 都从下标1开始使用
int main() {

	int n;//接收数组的元素个数
	int q;//接收查询次数
	cin >> n >> q;

	vector<int> arr(n); //创建arr数组来接受传进来的数组 从arr数组的下标0处开始接收
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	vector<long long> dp(n + 1);//预处理dp数组 dp数组从1开始存储元素
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1] + arr[i - 1];//公式变了
	}

	int l, r;//查询区间的左右边界

	while (q--) {//进行q次查询 没
		cin >> l >> r;
		cout << dp[r] - dp[l - 1] << endl;
	}

}
六：不推荐的写法
那这时候，就有人要问了，我就偏偏让arr和dp数组都从下标为0处开始使用，能不能写出代码通过呢？这种情况博主当然想到了，当然是可以的！不过这种写法，纯粹是胡~~~~~~闹！

首先不仅违背了bp[i]代表原生数组的前i个数的和意义，其次还多了两次的边界处理！所以你可以选择arr从0开始，但是千万不要选择前缀和数组dp从0开始！

#include <iostream>
#include<vector>
using namespace std;


//创建的arr 和 dp 都从下标0开始使用
int main() {

	int n;//接收数组的元素个数
	int q;//接收查询次数
	cin >> n >> q;

	vector<int> arr(n);//创建arr数组从0下标来接受传进来的数组
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	vector<long long> dp(n);//预处理dp数组，从0下标开始使用
	for (int i = 0; i < n; i++) {
		if (i == 0) dp[i] = arr[i];//对i为0 造成dp[i - 1]--->dp[-1]的处理
		else
			dp[i] = dp[i - 1] + arr[i];
	}

	int l, r;//查询区间的左右边界

	while (q--) {//进行q次查询 没
		cin >> l >> r;
		if (l == 1)//对l-1--> dp[-1]越界的处理
			cout << dp[r - 1] - 0 << endl;
		else
			cout << dp[r - 1] - dp[l - 2] << endl;
	}
}
//dp[i]：代表在arr数组中，i-1及其i-1左侧所有元素和

解释：可能这样唯一有意思的地方在于，我们的dp和arr数组又对其了，因为两个数组都是从0开始使用，所以求bp[i]的公式，用的是 dp[i] = dp[i - 1] + arr[i]; 哈哈哈哈哈哈哈!!

​